Concurrencia: exclusión mutua y sincronización. Comunicación entre procesos (página 2)

Partes: 1, 2

1 Programación concurrente.
Alternancia estricta.
Una variable (turn) controla el acceso de cada proceso.
El proceso saliente de la SC cambia el valor de la variable. El turno se lo pasa al otro proceso.
Los procesos realizan una espera ocupada.
La alternancia estricta obliga a la espera de un proceso aunque el otro no entre. Los dos procesos han de realizar el mismo número de entradas en la SC.
Proceso lento y no válido para procesos con ritmo distinto.
Infringe las reglas 3 y 4:
“No puede permitirse el interbloqueo o la inanición”.
“Ningún proceso fuera de su SC puede bloquear a otro.”
1.1. Soluciones por software (2).
(Gp:) while (true) {
while (turn!=0) /* espera */
sección_critica();
turn=1;
zona_no_crítica();
}
(Gp:) while (true) {
while (turn!=1) /* espera */
sección_critica();
turn=0;
zona_no_crítica();
}

1 Programación concurrente.
Señal de interés.
1.1. Soluciones por software (3).
while (TRUE)
{
señal[0]= TRUE;
while (señal[1]=TRUE) /* Bucle de espera */
sección_critica();
señal[0]= FALSE;
}
while (TRUE)
{
señal[1]= TRUE;
while (señal[0]=TRUE) /* Bucle de espera */
sección_critica();
señal[1]= FALSE;
}
Problema si ambos proceso ponen su señal igual a TRUE a la vez.

1 Programación concurrente.
Solución de Peterson (1).
Se incorporan variables para informar del otro proceso. Cada proceso pide la entrada en la SC con su número de proceso (llamada a la función).
Cuando un proceso muestra su interés por entrar y ve al otro interesado se bloquea.
El proceso espera hasta la entrada.
P0 pide la entrada (informa de que está interesado[0]=TRUE).
P1 ha de esperar hasta que interesado[0]= FALSE
Esto se produce con la salida de P0.
En caso de conflicto (P0 y P1 solicitan la entrada) el último espera. La variable turn resulta sobre-escrita.
1.1. Soluciones por software (4).

1 Programación concurrente.
#define FALSE 0
#define TRUE 1
#define N 2 /* Número de procesos */

int turn;
int interesado [N];

void entrada_a_la_sec (int proceso) /* El proceso entra indicando su número*/
{
int otro;
otro = 1- proceso;
interesado[proceso] = TRUE;
turn = proceso;
while ((turn == proceso) && (interesado[otro] == TRUE)) /* Bucle de espera */;
}

void salir_de_la_sec( int proceso)
{
interesado[proceso] = FALSE;
}

1.1. Soluciones por software (5).
Solución de Peterson (2).

1 Programación concurrente.
Desconexión de IRQs:
Antes de entrar en la SC se permite al proceso desconectar las IRQs.
Se evita su desplanificación.
Problema:
Mucho control sobre el sistema para procesos de usuario.
Problemas en sistemas paralelos. Otro proceso puede estar ejecutandose en otra CPU.
Solo es válido para algunos procesos del núcleo.
1.2. Soluciones por hardware (1).

1 Programación concurrente.
Test and Set Lock (TSL) / Comparar y fijar (1).
Se hace uso del hardware.
Control de un registro (MEM). Variable cerrojo.
Se realizan en un único ciclo de instrucción.
No están sujetas a injerencias por parte de otras instrucciones.
Leer y escribir.
Leer y examinar.
De forma indivisible se chequea el valor del registro y se cambia si procede la entrada en la SC. enter(SC) .
A la salida el proceso ha de devolver la variable a su valor de libre. leave(SC)
En el caso de multiprocesadoras se ha de cerrar el BUS de acceso a MEM durante el Test.
Observaciones:
El proceso a entrar realiza un espera ocupada.
Las llamadas de enter(SC) y leave(SC) se han de realizar en el orden correcto.
Se realiza espera ocupada.
Problemas cuando las prioridades de los procesos son muy dispares.

1.2. Soluciones por hardware (2).
boolean TS( int i)
{
if (i==0)
{
i=1;
return TRUE;
}
else
{
return FALSE;
}
}

1 Programación concurrente.
Test and Set Lock (TSL) / Comparar y fijar (2).
Ventajas:
Es aplicable a cualquier número de procesos en sistemas con memoria compartida, tanto de monoprocesador como de multiprocesador.
Es simple y fácil de verificar.
Puede usarse para disponer de varias secciones críticas.
Desventajas:
La espera activa consume tiempo del procesador.
Puede producirse inanición cuando un proceso abandona la sección crítica y hay más de un proceso esperando.
Interbloqueo:
Si un proceso con baja prioridad entra en su sección crítica y existe otro proceso con mayor prioridad, entonces el proceso cuya prioridad es mayor obtendrá el procesador para esperar a poder entrar en la sección crítica.

1.2. Soluciones por hardware (3).

1 Programación concurrente.
Función swap/intercambio.
Intercambio indivisible de la información entre un registro de la CPU y una variable.
Válida para varios procesos.
Cada proceso dispone de una variable cerrojo = 1.
La entrada a la sección crítica va precedida por el intercambio del valor de la variable con el de un registro en la CPU que inicialmente tiene un valor registro = 0.
1.2. Soluciones por hardware (4).
n es el número de procesos

1 Programación concurrente.
Se emplea espera activa.
Revisión continua del valor de la variable para ver si se tiene acceso a la SC.
Posible inanición
Selección arbitraria entre los procesos en espera.
Algún proceso puede no ser seleccionado nunca.
Posible interbloqueo.
Dos procesos uno en la SC y con baja prioridad (no planificable) y otro a la espera con alta prioridad.
1.2. Soluciones por hardware Problemas (5).

1 Programación concurrente.
Soluciones previas: Sleep() y wakeup()
Evitan la espera ocupada.
El proceso que no puede entrar en la SC se duerme: no es planificado (no consume tiempo de CPU).
El proceso saliente de la SC ha de despertar al proceso durmiente.
Problema ejemplo: Productor-consumidor mediante buffer.
Premisas:
Dos procesos (P1, P2) comparten un buffer para su comunicación.
El buffer contiene N slots (finito).
P1 produce información y la situa en el buffer hasta que este está lleno. => sleep()
P2 retira información del buffer hasta que este está vacío. => sleep()
P1 despierta si el buffer vuelve a tener huecos.
P2 despierta si el buffer vuelve a tener información.
Se define una variable count que almacena el número de slots con información.

1.3. Soluciones por semáforos.

1 Programación concurrente.
#define N 100

int count = 0;

void productor (void)
{
int item;
while (TRUE){
produce_un_elementos(&item);
if (count == N) sleep();
depositar_elemento (item);
count = count +1;
if (count == 1) wakeup(consumidor);
}
}

void consumidor (void)
{
int item;
while (TRUE){
if (count == 0) sleep();
obtener_un_elementos (&item);
count = count – 1;
if (count == N-1) wakeup(productor);
consumir_elemento (item);
}
}
1.3. Soluciones por semáforos.
Soluciones previas: sleep() y wakeup()

Problema
El proceso P2 es desplanificado tras chequear el valor de la variable count=0, se dispone a bloquearse (dormir) pero antes …
El consumidor P1 es planificado y genera información, count=1
Señal wakeup() al P2.
P2 no está todavía dormido. Se pierde la señal.
P2 vuelve a ser planificado y recuerda el valor count=0 => sleep().
P1 genera info. Llena el buffer => sleep()

Solución pasa por una variable que almacene el número de wakeup() emitidos/perdidos.
1 Programación concurrente.
Soluciones previas: sleep() y wakeup()
1.3. Soluciones por semáforos.

1 Programación concurrente.
Semáforo
Variable capaz de almacenar el número de wakeup() emitidos.
Los chequeos y cambio de variable:
Indivisibles. Operación única. Acción atómica.
Mediante llamadas al sistema (el sist. desconecta las IRQs).
En el caso de multiprocesadoras los semáforos han de ser operados mediante TSL.
Cada semáforo incorpora una cola con los procesos FIFO (robusto) o sin un orden específico (débil).

Operadores:
down() => sleep()
up() => wakeup()

up() => semáforo++;
down() => chequea el valor de la variable.
Si semáforo=0 => proceso a dormir sleep();
Si semáforo>0 => semáforo–;
1.3. Soluciones por semáforos.

1 Programación concurrente.
Productor consumidor con semáforos.
3 semáforos:
full : número de slots ocupados (0).
empty : número de slots libres (N).
mutex: control el acceso del proceso (1). Garantiza la exclusión mutua.
Cada semáforo se asocia con un dispositivo o recurso.
1.3. Soluciones por semáforos.
(Gp:) #define N 100
semaphore mutex=1;
semaphore empty=N;
semaphore full=0;
void producer()
{
int item;
while (TRUE){
produce_item(&item);
down(&empty);
down(&mutex);
enter_item(item);
up(&mutex);
up(&full);
}
}
(Gp:) void consumidor()
{
int item;
while (TRUE){
down(&full);
down(&mutex);
remove_item(item);
up(&mutex);
up(&empty);
}

Contadores de eventos
No necesitan la exclusión mutua.
Operación:
read(E) => lee E
advance (E) => E++
await(E,v) => espera hasta que E ? v

Solo incrementos.
Valor inicial = 0.
Dos variables: se controla la diferencia.
in => los que entran
Out => los que salen.

1 Programación concurrente.
Mecanismo de mayor abstracción: Módulo de software.
Características básicas:
Las variables de datos locales están sólo accesibles para el monitor.
Un proceso entra en el monitor invocando a uno de sus procedimientos.
Sólo un proceso se puede estar ejecutando en el monitor en un instante dado.
Módulo formado por:
Procedimientos.
Variables.
Estructuras de datos.

Eliminan la posibilidad de error por imponer el orden de los semáforos.
Todo acceso se hace mediante las funciones que entrega el monitor. No hay acceso directo al interior.
El sistema garantiza que solo existe un proceso activo dentro del monitor.
El compilador construye las llamadas y la exclusión.
1.4. Monitores.

1 Programación concurrente.
Funciones para bloqueo:
wait() y signal(): Dentro del monitor, sobre las variables del sistema.
signal:
Despierta al proceso durmiente en la variable.
Es la última instrucción que se ha de ejecutar antes de salir del monitor. Exclusión mutua.
No son muy acumulativos. Las señales a un proceso que no espera se pierden.
wait y signal: exclusión mutua automática.
sleep y wakeup: necesitan exclusión mutua.
1.4. Monitores.

1 Programación concurrente.
El intercambio de información entre procesos necesita:
Buffer compartido.
Código específico. El programador ha de conocer todos los detalles.
La comunicación mediante mensajes.
No necesitan compartir memoria.
Se ha de considerar:
Comunicación directa ó indirecta.
Bidireccional ó unidireccional.
Buffering automático o explicito.
Por copia o por referencia.
Tamaño del mensaje fijo o variable.
1.4. Canales de Comunicación.

1 Programación concurrente.
Nombres:
Se enuncia explícitamente el destinatario o emisor del mensaje.
Se definen primitivas del tipo:
send(proc, mensaje);
receive (proc, mensaje);
Propiedades:
Vínculo automático de los procesos en comunicación con solo conocer la identidad del otro proceso.
Comunicación de proceso a proceso (dos).
Válido sólo para dos procesos.
Para un par de procesos existe sólo un vínculo.
El vínculo puede ser bidireccional o unidireccional.
Problema: El cambio de nombre de los procesos.

1.4. Canales de Comunicación. Comunicación directa

1 Programación concurrente.
Se usan buzones o puertos.
Cada buzón posee un identificador.
Se permiten varios buzones.
Los buzones han de estar compartidos.
Primitivas:
send(puzón, mensaje);
receive (buzón, mensaje);
Propiedades:
La comunicación se realiza sólo si existe un buzón común.
Se permite el establecer un vínculo con dos o más procesos.
Para dos o más proceso comunicándose pueden existir varios vínculos. 1link? 1 buzón.
Comunicación unidireccional y bidireccional.

1.4. Canales de Comunicación. Comunicación indirecta.

1 Programación concurrente.
Usuario.
El buzón desaparece con el proceso que lo inicia.
Sistema Operativo.
Existencia propia.
No está vinculado a ningún proceso.
El S.O. permite:
Crear buzones.
Envío y recepción de mensajes.
Destrucción de buzones.
1.4. Canales de Comunicación. Pertenencia del buzón.
Capacidad.
Existe un número máximo de mensajes que se pueden almacenar en el buzón.
Tipos:
Capacidad 0:
Longitud máxima = 0.
No puede retener ningún mensaje.
Sincronización entre procesos emisor y receptor.
Capacidad encadenada:
Longitud finita N.
Emisión mientras hay slots libres.
Capacidad no encadenada:
Longitud infinita.

1 Programación concurrente.
Se necesita un canal seguro: encriptación.
Identificación
proceso@máquina, máquina:proceso
Problemas de saturación, duplicidad o consistencia.
Dominios:=> proceso@máquina.uah.es
Número random de 64 bits.

Definiciones:
Mensaje:
Parte de la información que es pasada de un proceso a otro.
Buzón:
buffer de almacenamiento de mensajes desde que llegan a la máquina hasta que son retirados por el proceso consumidor.
1.4. Canales de Comunicación. Identificación.

1 Programación concurrente.
Estructura del mensaje:
Cabeza: remite, destino, longitud, etc.
Cuerpo: información.
Mensaje:
No hay problema de compartir memoria entre procesos.
Permite la computación distribuida.
No se necesita coordinar los programadores de los distintos módulos.
Se necesita un protocolo de comunicación común.
Existen más posibilidades de pérdida de mensajes.
Problemas en los procesos (hang)
Demoras en espera de comunicación por parte del sistema de problema o espera de time out.
Pérdida de mensajes por la red.
El SO ha de descubrir el error y reenviar el mensaje.
El proceso emisor ha de comprobar la recepción y repetir.
El SO detecta el problema y notifica la necesidad de repetir.

Depende de Sistema y usuario que se detecten las pérdidas.
Otro problema es la recepción del asentimiento.
Posible solución es el Nº de mensaje.

1.4. Canales de Comunicación. Mensajes

Mecanismos de comunicación
Señales.
Asíncronas.Indican activación de un evento.
Tuberías.
Camino continuo de comunicación entre dos procesos.
FIFO.
La gestión la realiza el SO.
Las crea el proceso que ha de comunicarse y desaparecen con él.
Las tuberías con nombre permanecen. Son similares a un archivo.
Colas de mensajes.
Comunicación continua entre procesos.
Se tratan como zonas de memoria ? problemas de tamaño.
Semáforos.
Sincronización entre procesos que comparten recursos.
Mantienen sección crítica.
Asociados a los recursos.
Memoria compartida.
Zona de memoria accesible simultáneamente por varios procesos.
Acceso aleatorio: exige el conocimiento por parte de los procesos de la estructura de la información que contiene.
Acceso rápido, efectivo, flexible.
Válido para varios procesos.
La zona viene asociada a un semáforo.
Buzones (sockets).
Similares a tuberías.
Comunican procesos situados en distintos nodos de la red.